package binaryTree.review;

public class MergeSort {

    public int[]  mergeSort(int[] nums){
        if (nums.length==0){
            return  null;
        }
      int [] temp=new int[nums.length];
        sort(nums,0, nums.length-1,temp);
        return  nums;
    }


    public void sort(int[] nums,int lo,int hi,int[] temp){
        if (lo>=hi){
            return;   //todo:归并排序就是后序遍历　　　快速排序类似前序遍历
        }
        int mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        //todo：merge 函数有　lo  mid  hi 才合理　
        merge(nums,lo,mid,hi,temp);
    }


    public  void merge(int [] nums,int lo,int mid,int hi,int[] temp){
      int i=0;
      int j=lo;
      int k=mid+1;
      while (j<mid+1&&k<=hi){
          if (nums[j]<nums[k]){
              temp[i++]=nums[j++];
          }
          else {
              temp[i++]=nums[k++];
          }
      }
        while (j<mid+1){
            temp[i++]=nums[j++];
        }
        while (k<=hi){
            temp[i++]=nums[k++];
        }
        for(int t=0;t<i;t++){
            nums[lo+t] = temp[t];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] nums={5,2,1,6,4};
        mergeSort.mergeSort(nums);

        for (int a: nums
             ) {
            System.out.println(a);
        }


    }

}
